Image information, be it color or black and white, is commonly generated in a raster format where the raster comprises a plurality of gray level pixels, i.e. pixels that are defined by digital values, each value representing a gray level among a number of gray levels. Thus, in an 8 bit system, 256 levels of gray are present, where each level represents an increment of gray between black and white. In the case of color rasters, where three defining colors or separations each include 256 levels of information, there may be more than 16 million colors defined by a gray bitmap. Some image output terminals (lOTs) typically print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is necessary to reduce the gray level image data to a limited number of levels so that it can be printed. Digital halftoning methods provide a method of rendering images having a continuum of grays on binary image output terminals (lOTs) such as electronic printers.
One standard method for converting gray level pixel values to binary level pixel values is through the use of dithering or halftoning. In such arrangements, patterns of black and white dots, which appear gray when viewed from a distance, are used to represent different levels of gray. These dots or halftone cells are typically formed from binary pixels which are the smallest reproducible black or white picture elements of lOTs. Thus, halftoning defines various levels of gray using different distribution of binary pixels in each halftone cell. In general, halftoning can be described using the boolean valued function: EQU H.sub.1 (x, y, d)=d&gt;T(x MOD M, y MOD N),
which determines if a pixel or an area of pixels at position (x, y) in a gray image should be black or white. The function H.sub.1 (x, y, d) compares the darkness or depth d of the gray pixel or area at position (x, y) with a threshold value T of a predetermined halftone cell (M.times.N) replicated to cover the image. Since this function must be applied to every pixel in the gray image it must be simple and quick to calculate using hardware or software.
A number of different threshold patterns have been used to describe a halftone cell or dot as shown in FIG. 15. These threshold patterns indicate the order in which pixels are switched from white to black to form dots of varying gray density. Typically, a threshold pattern can be classified as either a disperse dot or a cluster dot, examples of which are dots 90 and 91, respectively. Besides generating different formations of halftone dots for an identical gray image area, the halftoning method used to apply the disperse or cluster threshold pattern to the image area also results in different formations of halftone dots being generated. For example, each 4-bit pixel in an area of gray image data 92 can be halftoned using a dither method (e.g. partial dotting). Using the dither method, each gray pixel in the cell 92 is compared to disperse dot threshold pattern 90 or the cluster dot threshold pattern 91 in accordance with the function H.sub.1 (x, y, d) to produce halftone areas 94 and 95, respectively. Halftone areas 94 and 95 are grown incrementally, since each dot in the halftone cell is evaluated individually. Alternatively using a template dot or density pattern method, the gray image area 92 could be represented using its average gray density 9 in image area 93, which would result in the halftone areas 96 and 97 when thresholded using halftone threshold patterns 90 and 91, respectively.
Using either the dither method or density pattern method, described above, gray density of a binary image increases as more of the pixels in a halftone dot or cell are colored black. Also when pixels are added to a halftone dot one by one using either the disperse or cluster threshold pattern, the number of gray density levels for a binary image is given by the number of pixels in the halftone cell plus one (i.e. gray levels=1+mn). A fundamental drawback of these halftone methods is a tradeoff that exists between the number of gray levels in a halftone cell (fidelity) and resolution of the reproducing device which are traditionally binary, such as printers. Reducing the size of the halftone cell to include fewer pixels increases the effective resolution of a binary image while reducing the number of gray levels. Thus, an image reproduced with a high effective resolution will result in sharp detail, while an image reproduced with many intensity levels will result in very uniform grays or colors with high fidelity.
Halftoning presents problems since the amount of gray within an original image is not maintained exactly over an area, because the finite number of elements inside each halftone dot. The error arising from the difference between the output pixel value and the actual gray level pixel value at any particular cell is simply thrown away. This results in a loss of image information which introduces coarse quantization artifacts which are visible in the image areas where the scene has little variation. This is also known as "banding", and is caused by the limited number of output gray levels available. The "banding" artifacts generally increase with decreasing cell size, which is identical to a decrease in the number of levels that can be represented by a halftone cell.
Another problem associated with halftoning is that the shades of gray generated using a halftone cell on digital printing devices such as xerographic printers and thermal ink jet printers do not yield a visually linear progression of shades of gray. In fact the change from no dots in a matrix cell to one dot is a much more pronounced change in the visual perception of the shade then the change from one less than the maximum number of dots to the maximum number of dots. That is, each dot has a far greater visual effect at the light end of the tone scale than at the dark end. Consequently, fewer visually equal tones are possible than the number of dots in a halftone cell would at first suggest. In both xerography and ink jet printing attempts have been made to improve the image quality of the reproduced image.
Xerographic printers, for example, do not always render faithful copies of continuous tone originals, since typically such printers have a tone reproduction curve (TRC) with a steep slope due to either the discharge characteristic of the photoreceptor or the solid area development characteristic of the xerographic development system, or both. As a result, reproduced images may have washed-out highlights or overdeveloped shadows. At distances closer than the normal viewing distance, or when the size of the halftone cells are large, the quality of the reproduced picture is decreased. Just acceptable graininess requires at least 65 halftone cells per inch. A good quality halftone requires about 100 cells per inch. High quality (e.g., magazine type) requires about 150 cells per inch. A hybrid system consisting of a halftone with three or four gray levels is described in a publication entitled "Hybrid (Gray Pixel) Halftone Printing", by Lama et al. in the Journal of Imaging Technology, Vol. 15, no. 3, June, 1989.
Thermal ink jet printers, on the other hand, have used various approaches to control the overall halftone pattern by altering the size and spacing of individual ink drops to enhance the uniformity and consistency of halftone patterns. The various schemes include dot-on-dot and dot-next-to-dot techniques. Dot-on-dot techniques use identical halftone patterns for more than one color separation so that dots in those separations will be placed at the same location, while dot-next-to-dot techniques place the colors in a way that avoids overlap when possible. Both techniques are disclosed in the following U.S. Pat. Nos. 3,977,007; 4,280,144; 4,999,646; 5,016,191; 5,012,257; 4,746,935; 4,412,226; and 4,353,079 and U.S. Patent Application entitled "Ink Jet Printhead for Continuous Tone and Text Printing", to Rezanka, U.S. Ser. No. 08/000,375, filed Jan. 4, 1993.
Besides actually altering the physical device to provide an additional number of gray scale levels, techniques have been developed that enable the generation of halftone images with less textured background and better gray scale reproduction without losing resolution. A method of achieving multiple gradations for halftone imaging by arranging a specified number of dots in a plurality of ways (e.g. overlapping or non-overlapping dots) to obtain various gradations is published in JP-A 60-250774 to Inui on Dec. 11, 1985. IBM Technical Disclosure Bulletin Volume 23, No. 11, April 1981, pages 5225-5226, entitled "High Resolution Display and Printing Technique" by Yao, discloses a process for increasing image quality without increasing the number of pixels making up the image. The positions of pixels are perturbed to achieve smoother line images, while the total number of pixels in a field does not change. Every pixel may be positioned at one of several different locations. U.S. Pat. No. 4,593,297 to Suzuki et al. teaches that a plurality of image densities are rendered on a two-dimensional dot matrix basis by using a plurality of different gradation density patterns. Each gradation density pattern is determined by the number of dots employed and the direction of arrangement of the dots in the dot matrix.
Problems however exist with techniques that provide additional gray levels without increasing halftone cell size with patterns that are completely unrelated. Haftone patterns that are unrelated, even if they have almost the same gray level, have a tendency to cause noticeable discontinuities in the texture at the boundary between two halftone patterns. The halftone techniques that increase the number of available density patterns typically use arbitrary halftone cell patterns rather than patterns formed by incremental cell growth (or partial dotting). Using incremental cell growth with such halftoning techniques complicate the halftone function: EQU H.sub.2 (x, y, d)=d&gt;T(d, x MOD M, y MC)D N),
since the thresholds T(d, m, n) must be indexed by darkness or depth d as well as the position of each gray pixel. Additionally indexing depth d requires additional storage and index computation above that required for halftone function H.sub.1 (x, y, d). For example, simple increments and compares in halftone function H.sub.1 (x, y, d) are substituted in halftone function H.sub.2 (x, y, d) for MOD operations that are more computationally difficult.